package battlestein;

import java.util.*;

/**
 * 
 * @author LocoRocoBattleStein
 *
 */
public class Graph {

	int[] edges;
	int[] neighbours;
	int[] weights;
	
	int[][] dijkstraPath;
	/**
	 * Constructor
	 * @param edges
	 * @param neighbours
	 * @param weights
	 */
	public Graph(int[] edges, int[] neighbours, int[] weights) {
		this.edges = edges;
		this.neighbours = neighbours;
		this.weights = weights;
		
		dijkstraPath = new int[edges.length][];
		for(int i=0; i<edges.length; i++) {
			dijkstraPath[i] = dijkstra(i);
		}
	}
	
	public int[] shortestPath(int src, int dest) {
		LinkedList<Integer> path = new LinkedList<Integer>();
		path.add(dest);
		int i = dest;
		while(i != src) {
			i = dijkstraPath[src][i];
			path.add(0,i);
		}
		
		int[] shortest = new int[path.size()];
		for(int j=0; j<shortest.length; j++) {
			shortest[j] = path.get(j).intValue();
		}
		return shortest;
	}
		
	// Dijkstra's algorithm to find shortest path from s to all other nodes
	   public int [] dijkstra (int s) {
	      final int [] dist = new int [edges.length];  // shortest known distance from "s"
	      final int [] pred = new int [edges.length];  // preceeding node in path
	      final boolean [] visited = new boolean [edges.length]; // all false initially

	      for (int i=0; i<dist.length; i++) {
	    	  dist[i] = Integer.MAX_VALUE;
	      }
	      dist[s] = 0;

	      for (int i=0; i<dist.length; i++) {
	    	  final int next = minVertex (dist, visited);
	    	  visited[next] = true;

	    	  // The shortest path to next is dist[next] and via pred[next].

	    	  final int [] n = getNeighboursEdge(next);
	    	  for (int j=0; j<n.length; j++) {
	    		  final int v = n[j];
	    		  final int d = dist[next] + getWeightEdges(next,v);
	    		  if (dist[v] > d) {
	    			  dist[v] = d;
	    			  pred[v] = next;
	    		  }
	    	  }
	      }
	      return pred;  // (ignore pred[s]==0!)
	   }

	   private static int minVertex (int [] dist, boolean [] v) {
	      int x = Integer.MAX_VALUE;
	      int y = -1;   // graph not connected, or no unvisited vertices
	      for (int i=0; i<dist.length; i++) {
	    	  if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
	      }
	      return y;
	   }
	   
	   public int[] getNeighboursEdge(int edge) {
		   int[] ngb;
	 
		   if(edge<(edges.length-1)) ngb = new int[edges[edge+1] - edges[edge] - 1];  
		   else ngb = new int[neighbours.length - edges[edge] - 1];
		   
		   for(int i=0; i<ngb.length; i++) {
			   ngb[i] = neighbours[edges[edge]+i];
		   }
		   return ngb;
	   }
	   
	   public int getWeightEdges(int edge1, int edge2) {
		   int i = edges[edge1];
		   while(neighbours[i] != -1) {
			   if(neighbours[i] == edge2) return weights[i];
			   i++;
		   }
		   return -1;
	   }

	   public static void main(String[] args) {
			int[] edges = {0,4,7,10};
			int[] neighbours = {1,2,3,-1,0,3,-1,0,3,-1,0,1,2};
			int[] weights = {2,1,3,-1,2,2,-1,1,1,-1,3,2,1};
			Graph graph = new Graph(edges,neighbours,weights);
			
			int[] shortest = graph.dijkstra(0);
			for(int j=0;j<shortest.length;j++) {
				System.out.println(shortest[j]);
			}
		}
	
	

}
